#include <stdio.h>
#include <stdlib.h>
//二叉树的层次遍历：求一个二叉树的深度
#define MAXSIZE 100     //使用循环队列，防溢出
char expr[]="ABDH#K###E##CFI###G#J##"; //按照前序顺序写的数组
int i=0; //用来遍历数组
typedef char ElemType;
//1️⃣二叉树结点的声明
typedef struct bitree
{
    ElemType data;
    struct bitree *lchild;
    struct bitree *rchild;
}BiTree;
//2️⃣创建二叉树
void creatbitree(BiTree **t)
{
    ElemType symbol=expr[i++];
    if(symbol=='#')
    {
        *t=NULL;
    }
    else
    {
        *t=(BiTree *)malloc(sizeof(BiTree));
        (*t)->data=symbol;
        creatbitree(&(*t)->lchild);
        creatbitree(&(*t)->rchild);
    }
}
//4️⃣创建一个循环队列
//声明
typedef struct 
{
    BiTree *data[MAXSIZE]; //指针数组，存放BiTree *类型指针，把指向结点的指针入队
    int front;
    int rear;
}Queue;
//初始化
void initqueue(Queue *q)
{
    q->front=0;
    q->rear=0;
}
//入队
void push(Queue* q,BiTree *n)
{
    if((q->rear+1)%MAXSIZE==q->front)
    {
        printf("队满了\n");
    }
    q->data[q->rear]=n;
    q->rear++;
}
//判断队是否为空队
int isempty(Queue *q)
{
    if(q->rear==q->front)
    return 0;
    else
    return 1;
}
//获取队内元素个数
int countqueue(Queue *q)
{
    return q->rear-q->front;
}
//出队
void pop(Queue *q,BiTree **ret)
{
    *ret=q->data[q->front];
    q->front++;
}
//3️⃣求深度
int maxdepth(BiTree *t)
{
    int dep=0; //用来记录深度
    BiTree *ret; //用来存放出队元素的信息，以便找到其左右孩子入队
    Queue q;
    initqueue(&q);
    push(&q,t); //把根结点的元素入队
    while(isempty(&q))
    {
        int count=countqueue(&q);
        while(count>0)
        {
            pop(&q,&ret);  //二级指针，存储出栈元素指针
            count--;
            if(ret->lchild!=NULL)
            {
                push(&q,ret->lchild);
            }
            if(ret->rchild!=NULL)
            {
                push(&q,ret->rchild);
            }
        }
        dep++;
    }
    return dep;
}
int main()
{
    BiTree *t=NULL;
    creatbitree(&t);
    printf("%d\n",maxdepth(t));
    return 0;
}

//注意，是把二叉树结点的指针入队